# 给定一个二维矩阵 matrix，以下类型的多个请求： 
# 
#  
#  计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。 
#  
# 
#  实现 NumMatrix 类： 
# 
#  
#  NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化 
#  int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下
# 角 (row2, col2) 所描述的子矩阵的元素 总和 。 
#  
# 
#  
# 
#  示例 1： 
# 
#  
# 
#  
# 输入: 
# ["NumMatrix","sumRegion","sumRegion","sumRegion"]
# [[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,
# 1,2,2],[1,2,2,4]]
# 输出: 
# [null, 8, 11, 12]
# 
# 解释:
# NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,
# 0,1,7],[1,0,3,0,5]]);
# numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
# numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
# numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)
#  
# 
#  
# 
#  提示： 
# 
#  
#  m == matrix.length 
#  n == matrix[i].length 
#  1 <= m, n <= 200
#  
#  -10⁵ <= matrix[i][j] <= 10⁵ 
#  0 <= row1 <= row2 < m 
#  0 <= col1 <= col2 < n 
#  
#  最多调用 10⁴ 次 sumRegion 方法 
#  
# 
#  Related Topics 设计 数组 矩阵 前缀和 👍 587 👎 0
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        self.n = matrix
        m = len(self.n)
        n = len(self.n[0])
        self.arr = [[x for x in row] for row in self.n]
        """
        初始化完成后的效果就是：
        第一列：所有格子对应从左上角到当前格子的元素和
        其它格子：表示当前行第一个元素到自身的和
        """
        # 初始化除开第一列外的元素,在每一行,当前元素表示从该行第一个到当前元素的和
        for i in range(m):
            for j in range(1, n):
                self.arr[i][j] += self.arr[i][j - 1]
        # 初始化第一列，注意，第一列要最后在算出来
        for i in range(1, m):
            self.arr[i][0] += self.arr[i - 1][0]
        """
        最后，self.arr里当前元素的值+上方元素的值即为从左上角到当前元素的和
        """
        for i in range(1, m):
            for j in range(1, n):
                self.arr[i][j] += self.arr[i - 1][j]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        # 开始和结束在同一个格子
        if row1 == row2 and col1 == col2:
            return self.n[row1][col1]
        # 开始格子为数字第一个元素
        elif row1 - 1 < 0 and col1 - 1 < 0:
            return self.arr[row2][col2]
        # 开始格子下方没有元素
        elif row1 - 1 < 0 <= col1 - 1:
            return self.arr[row2][col2] - self.arr[row2][col1 - 1]
        #  开始格子左边没有元素
        elif col1 - 1 < 0 <= row1 - 1:
            return self.arr[row2][col2] - self.arr[row1 - 1][col2]
        # 重叠了一个部分，也就是减去了两次重叠部分，需要加上一次
        else:
            return self.arr[row2][col2] - self.arr[row1 - 1][col2] - self.arr[row2][col1 - 1] + self.arr[row1 - 1][
                col1 - 1]


# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)
# leetcode submit region end(Prohibit modification and deletion)
print(NumMatrix([[-4, -5]]).sumRegion(
    0, 0, 0, 1))
"""
测试用例:["NumMatrix","sumRegion","sumRegion","sumRegion"]
			[[[[-4,-5]]],[0,0,0,0],[0,0,0,1],[0,1,0,1]]
	测试结果:[null,-4,0,-9]
	期望结果:[null,-4,-9,-5]
"""
